Running times are the median of five runs on an UltraSparc II (296MHz CPU, 256Mb RAM).

Running times are the median of five runs on an UltraSparc II (296MHz CPU, 256Mb RAM).

This allows for the representation and exact solution of a wide range of problems in which transitions or rewards vary over time. We examine problems based on route planning with public transportation andtelescope observation scheduling. 1 Introduction Imagine trying to plan a route from home to work that minimizes expected time. One approach is to use a tool such as "Mapquest", which annotates maps with information about estimated driving time, then applies a standard graph-search algorithm to produce a shortest route. Even if driving times are stochastic, the annotations canbe expected times, so this presents no additional challenge. However, consider what happens if we would like to include public transportation in our route planning. Buses, trains, and subways vary in their expected travel time according to the time of day: buses and subways come more frequently during rush hour; trains leave on or close to scheduled departure times. In fact, even highway driving times vary with time of day, with heavier traffic and longer travel times during rush hour.